package 哈希表;

import org.junit.Test;

import java.util.Arrays;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/3/7 16:50
 */
public class leetcode645原地哈希 {

    /*
      利用 这个 题 , 弄清楚  原地 哈希的 原理:
      和 使用场景
     */
    private void swap(int nums[],int i,int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    /*
     这 中 写法 是 把 所有的 元素(除了 重复的 )
     都 正确  归位!
     */


    public int [] solution(int nums[]){
        for(int i = 0;i < nums.length;i++){
            while(nums[i] != i + 1 && nums[i] != nums[nums[i] - 1]){
                swap(nums,i,nums[i] - 1);
            }
        }
        int ans [] = new int[2];
        for(int i = 0;i < nums.length;i++){
            if(nums[i] != i + 1){
                ans[0] = nums[i];
                ans[1] = i + 1;
            }
        }
        return ans;
    }



    /*
      正确的 写法,
      算了吧 ,就使用了 上面的 算法去写 得了!
     */






    /*
    但是 ,并不用 把 所有的元素 ,都正确的 归位, 只需要找到重复的 元素 即可
    可以 按照 下面的 写法:
    这种 写法是有问题 的  error case : [3,2,2] 就会报错
     */

    public int []solution1(int nums[]){

        int repeat = 0,sum = 0,shouldSum = 0;
        sum = Arrays.stream(nums).sum();
        for(int i = 0;i < nums.length;i++){
            if(nums[i] != i + 1){
                if(nums[i] != nums[nums[i] - 1]){
                    swap(nums,i,nums[i] - 1);
                }
                else{
                    repeat = nums[i];
                    break;
                }
            }
        }
        return new int[]{repeat,( 1 + nums.length) * nums.length / 2 + repeat - sum};
    }


    @Test
    public void test(){
        int nums[] = {1,2,2,4};
        solution1(nums);
    }

}
